package com.leetcode.p200;

import java.util.ArrayList;
import java.util.Arrays;

public class Test279 {

    public int numSquares(int n) {
        ArrayList<Integer> nums = new ArrayList<>();

        for (int i = 1; i <= n; i++) {
            int num = i * i;
            if (num <= n) {
                nums.add(num);
            } else {
                break;
            }
        }

        int[] results = new int[n + 1];
        Arrays.fill(results, n + 1);
        results[0] = 0;

        int amount = n + 1;

        for (int i = 1; i < amount; i++) {
            for (int j = 0; j < nums.size(); j++) {
                if (nums.get(j) <= i) {
                    results[i] = Math.min(results[i], results[i - nums.get(j)] + 1);
                }
            }
        }

        return results[n] > n ? -1 : results[n];
    }

    public static void main(String[] args) {

        Test279 test = new Test279();
//        int result = test.numSquares(12);
        int result = test.numSquares(1);
        System.out.println(result);
    }

}
